package com.huawei.su;

import java.util.Stack;

public class BM8 {


    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode = FindKthToTail(listNode1, 5);
        System.out.println(listNode);
    }

    private static ListNode FindKthToTail(ListNode pHead, int k) {
        ListNode index1 = pHead;
        ListNode index2 = pHead;
        int i = 0;

        while (true) {
            if (index1 == null) {
                break;
            }
            if (i >= k) {
                index1 = index1.next;
                index2 = index2.next;
            } else {
                index1 = index1.next;
            }
            i++;
        }
        if (k > i) {
            return null;
        }
        return index2;
    }

    public static ListNode FindKthToTail1(ListNode pHead, int k) {
        // write code here
        ListNode index = pHead;
        Stack<ListNode> stack = new Stack<>();
        while (true) {
            if (index == null) {
                break;
            }
            stack.push(index);
            index = index.next;
        }

        int i = 1;
        while (true) {
            if (stack.isEmpty()) {
                break;
            }
            if (i == k) {
                return stack.pop();
            }
            stack.pop();
            i++;
        }
        return null;
    }
}
